/*
 * @lc app=leetcode.cn id=3152 lang=golang
 *
 * [3152] 特殊数组 II
 */
package Solutions

import (
	"slices"
)

// @lc code=start
func isArraySpecial(nums []int, queries [][]int) []bool {
	flag := nums[0]&1 == 0
	left := 0
	mp := make([][2]int, 0, len(nums)/2)
	for i := 0; i < len(nums); i++ {
		if (flag && nums[i]&1 == 0) || (!flag && nums[i]&1 != 0) {
			flag = !flag
		} else {
			mp = append(mp, [2]int{left, i - 1})
			left = i
		}
	}
	mp = append(mp, [2]int{left, len(nums) - 1})
	ans := make([]bool, 0, len(queries))
	for _, v := range queries {
		index, ok := slices.BinarySearchFunc(mp, v[0], func(sl [2]int, t int) int {
			return sl[0] - t
		})
		if !ok {
			index--
		}

		ans = append(ans, mp[index][1] >= v[1])
	}
	return ans

}

// @lc code=end
